//
// Created by Administrator on 2021/11/13.
//
#include <cstdio>
#include <cstdlib>

#define MaxSize 100//定义最大个数
#define ElemType int

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;//左孩子，右孩子指针
    struct BiTNode *parent;//父节点指针(方便寻找父结点，考研一般不爱考)
} BiTNode, *BiTree;

//线索二叉树结点
typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;//左、右线索标志
    /*tag==0表示指向孩子
     * tag==1表示指向线索*/
} ThreadNode, *ThreadTree;

BiTNode *p;//指向目标节点
BiTNode *pre = NULL;//指向当前访问节点的前驱
BiTNode *final = NULL;//用于记录最终访问结果

/*访问结点q（顺便找到前驱结点）*/
void visit(BiTNode *q) {
    if (q == p) {
        //当前访问结点刚好是目标结点p
        final = pre;//找到p的前驱
    } else {
        pre = q;//pre指向当前访问的结点（前驱结点向前移动）
    }
}

/***********************************************************************/
ThreadNode *Tp;//指向目标节点
ThreadNode *Tpre = NULL;//指向当前访问节点的前驱
ThreadNode *Tfinal = NULL;//用于记录最终访问结果

/*访问结点q（顺便找到前驱结点）*/
void visit(ThreadNode *q) {
    if (q == Tp) {
        //当前访问结点刚好是目标结点p
        Tfinal = Tpre;//找到p的前驱
    } else {
        Tpre = q;//pre指向当前访问的结点（前驱结点向前移动）
    }
}

//中序遍历二叉树，一边遍历一边线索化
void InThread(ThreadTree T) {
    if (T) {
        InThread(T->lchild);//中序遍历左子树
        visit(T);//访问根节点
        InThread(T->rchild);//中序遍历右子树
    }
}

/*****************************************************/
void Tvisit(ThreadNode *q) {
    if (q->lchild == NULL) {//左子树为空，建立前驱线索
        q->lchild = Tpre;
        q->ltag = 1;
    }
    if (Tpre != NULL && pre->rchild == NULL) {
        Tpre->rchild = q; //建立前驱结点的后继线索
        Tpre->rtag = 1;
    }
    Tpre = q;
}

//中序遍历二叉树，一边遍历一边线索化
void TInThread(ThreadTree T) {
    if (T) {
        TInThread(T->lchild);//中序遍历左子树
        Tvisit(T);//访问根节点
        TInThread(T->rchild);//中序遍历右子树
    }
}
/******************************************************/
//全局变量pre,指向当前访问结点的前驱
ThreadNode *Pre = NULL;

//中序线索化二叉树T
void CreateInThread(ThreadTree T) {
    Pre = NULL;//pre初始为NULL
    if (T != NULL) {
        //非空二叉树才能线索化
        TInThread(T);//中序线索化二叉树
        if (Pre->rchild == NULL) {
            Pre->rtag = 1;//处理遍历的最后一一个结点
        }
    }
}
/********************************************************/
//先序遍历二叉树，-边遍历-边线索化
void PreThread(ThreadTree T) {
    if (T != NULL) {
        Tvisit(T);//先处理根节点
        if (T->ltag == 0) {
            //左孩子未被线索化(防止转圈问题)
            PreThread(T->lchild);
        }
        PreThread(T->rchild);
    }
}

//全局变量pre,指向当前访问结点的前驱
ThreadNode *Prepre = NULL;

//先序线索化二叉树T
void CreatePreThread(ThreadTree T) {
    Prepre = NULL;//pre初始为NULL
    if (T != NULL) {//非空二叉树才能线索化
        PreThread(T);//先序线索化二叉树
        if (Prepre->rchild == NULL) {
            Prepre->rtag = 1;//处理遍历的最后一个结点
        }
    }
}
/**********************************************************/
/*中序线索二叉树找后继
* 在中序线索二叉树中找到指定结点*p的中序后继next
 * ①若p->rtag==1，则next = p->rchild
 * ②若p->rtag==O，p的后继=p的右子树中，最左下角的结点 */

/*找到以P为根的子树中，第一个被中序遍历的结点*/
ThreadNode *Firstnode(ThreadNode *p) {
    //循环找到最左下结点(不一定是叶结点)
    while (p->ltag == 0) {
        p = p->lchild;
    }
    return p;
}

/*在中序线索二叉树中找到结点p的后继结点*/
ThreadNode *Nextnode(ThreadNode *p) {
    //右子树中最左下结点
    if (p->rtag == 0) {
        return Firstnode(p->rchild);
    } else {
        return p->rchild;//rtag==1直接返回后继线索
    }
}

/*对中序线索二叉树进行中序遍历(利用线索实现的非递归算法)*/
void Inorder(ThreadNode *T) {
    for (ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p)) {
        visit(p);
    }
}
/**********************************************************/
/*在中序线索二叉树中找到指定结点*p的中序前驱pre
 * ①若 p->ltag==1，则pre = p->lchild
 * ②若p->ltag==O，则p的前驱=p的左孩子的最右下的结点 */

//找到以P为根的子树中，最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p) {
    //循环找到最右下结点(不一定是叶结点)
    while (p->rtag == 0) {
        p = p->rchild;
    }
    return p;
}

//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p) {
    //左子树中最右下结点
    if (p->ltag == 0) {
        return Lastnode(p->lchild);
    } else {
        return p->lchild;////ltag == 1直接返回前驱线索
    }
}

//对中序线索二叉树进行逆向中序遍历
void RevInorder(ThreadNode *T) {
    for (ThreadNode *p = Lastnode(T); p != NULL; p = Prenode(p)) {
        visit(p);
    }
}

/*在先序线索二叉树中找到指定结点*p的先序后继next
 * ①若p->rtag==1，则next = p->rchild
 * ②若p->rtag==O，如果p有左孩子，p的后继=左孩子，否则=右孩子*/

/*在先序线索二叉树中找到指定结点*p的先序前驱pre
 * ①若p->ltag==1，则next = p->lchild
 * ②若p->ltag==O（4种情况）
 *
 *①如果能找到p的父节点，且p是左孩子
 * p的父节点即为其前驱
 *
 * ②如果能找到p的父节点，且p是右孩子，其左兄弟为空
 * p的父节点即为其前驱
 *
 * ③如果能找到p的父节点，且p是右孩子，其左兄弟非空
 * p的前驱为左兄弟子树中最后一个被先序遍历的结点
 *
 * ④如果p是根节点
 * p没有先序前驱
 * */

/*在后序线索二叉树中找到指定结点*p的后序前驱pre
 * ①若p->ltag==1，则 pre = p->lchild
 * ②若p->ltag==O
 *
 * ①如果p有右孩子
 * 后序前驱为右孩子
 *
 * ②若p没有右孩子
 * 后序前驱=左孩子
 * */

/*在后序线索二叉树中找到指定结点*p的后序后继next
 * ①若p->rtag==1，则next = p->rchild
 * ②若p->rtag==O
 *
 * ①如果能找到p的父节点,且p是右孩子
 * p的父节点即为其后继
 *
 * ②如果能找到p的父节点，且p是左孩子，其右兄弟为空
 * p的父节点即为其后继
 *
 * ③如果能找到p的父节点，且p是左孩子，其右兄弟非空
 * p的后继为右兄弟子树中第一个被后序遍历的结点
 *
 * ④如果p是根节点
 * p没有先序前驱
*/

/*以上内容，自己理解会推，不需要死记硬背！*/